#include <cstdlib>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

const int row=3,col=2;

const int INVALID=-2;
const int LOWER=-1,HIGHER=1;
const int STGLEFT=2,STGOPER=3,STGRIGHT=4,STGENDING=5;

const char operTable[row][col]= {
	{'+','-'},
	{'*','/'},
	{'(',')'}
};

class node {
	public:
		node();
		void setleft(node *l) {
			left=l;
			l->father=this;
			l->isleft=true;
		}
		void setright(node *r) {
			right=r;
			r->father=this;
			r->isleft=false;
		}

		void setinbrac(bool b) {
			inbracket=b;
		}
		void setisroot(bool r) {
			isroot=r;
		}

		void setoper(char o) {
			isoper=true;
			oper=o;
		}
		void setnum(int n) {
			isoper=false;
			num=n;
		}

		bool getinbrac() {
			return inbracket;
		}
		bool getisroot() {
			return isroot;
		}
		bool getisoper() {
			return isoper;
		}
		bool getisleft() {
			return isleft;
		}

		char getoper() {
			return oper;
		}
		int getnum() {

			return num;
		}

		node* getfather() {
			return father;
		}
		node* getleft() {
			return left;
		}
		node* getright() {
			return right;
		}
		int getno(){
			return no;
		}
	private:
		bool inbracket,isroot,isoper,isleft;
		char oper;
		int num,no;
		node *father,*left,*right;
};

vector<node*> nodes;

node::node(){
	inbracket=isroot=isoper=isleft=false;
	oper='+';
	num=0;
	no=nodes.size();
	father=left=right=NULL;
}

string str;
int pos;

void end(){
	system("pause");
	exit(0);
}

void error(string str="") {
	if(str!="")
		cout<<str<<endl;
	cout<<"HSSCalc exit."<<endl;
	end();
}

bool cisnum(char c) {
	return c>='0'&&c<='9';
}

int getOperLevel(char c) {
	for(int i=0; i<row; i++) {
		for(int j=0; j<col; j++) {
			if(operTable[i][j]=='\0') {
				break;
			} else if(operTable[i][j]==c) {
				return i;
			}
		}
	}
	return INVALID;
}

bool cisoper(char c){
	return getOperLevel(c)!=INVALID&&c!='('&&c!=')';
}

void check() {
	int cnt=0;
	if(str=="")//TODO
		error("Empty string error.");
	for(int i=0; i<(signed int)str.length(); i++) {
		if(!cisnum(str[i])) {
			if(getOperLevel(str[i])==INVALID) {
				error("Invalid char error.");
			} else if(str[i]=='(') {
				cnt++;
			} else if(str[i]==')') {
				cnt--;
			}
		}
		if(cnt<0) {
			error("Invalid bracket error.");
		}
	}
	if(cnt!=0) {
		error("Invalid bracket error.");
	}
}

int getstage(node &n) {
	if(n.getleft()==NULL)
		return STGLEFT;
	else if(!n.getisoper())
		return STGOPER;
	else if(n.getright()==NULL)
		return STGRIGHT;
	else
		return STGENDING;
}

char nextchar() {
	if(pos>=(signed int)str.length()-1)
		return '\0';
	else
		return str[++pos];
}

int getStrNum() {
	int num=0;
	while(pos<(signed int)str.length()&&cisnum(str[pos])) {
		num=num*10+str[pos]-'0';
		pos++;
	}
	pos--;
	return num;
}

int opcomp(char op1,char op2){
	int level1=getOperLevel(op1);
	int level2=getOperLevel(op2);

	if(level1==INVALID){
		ostringstream oss;
		oss<<"Compare error, pos "<<pos<<",oper "<<op1<<".";
		error(oss.str());
	}
	if(level2==INVALID){
		ostringstream oss;
		oss<<"Compare error, pos "<<pos<<",oper "<<op2<<".";
		error(oss.str());
	}

	if(level1<level2)
		return LOWER;
	else
		return HIGHER;
}

void output(int num){
	cout<<num<<endl;
}

node* newnode(){
	node *n=new node();
	nodes.push_back(n);
	//cout<<"212:New node "<<n->getno()<<endl;
	return n;
}

void maketree(node &curr) {
	char inp;
	node *addleft;
	node *addright;
	node *addcomp;
	//cout<<"219:Now is node "<<curr.getno()<<endl;
	switch(getstage(curr)) {
		case STGLEFT:
			addleft=newnode();
			inp=nextchar();
			//cout<<"225:stage left pos "<<pos<<" inp "<<inp<<endl;
			if(cisnum(inp)) {
				addleft->setnum(getStrNum());
				curr.setleft(addleft);
			} else if(inp=='(') {
				addleft->setinbrac(true);
				curr.setleft(addleft);
				//cout<<"232:node "<<curr.getno()<<" give to "<<addleft->getno()<<endl;
				maketree(*addleft);
			} else {//error
				ostringstream oss;
				oss<<"236:Maketree error, pos "<<pos<<",Stage left.";
				error(oss.str());
			}
//No break,continue to process
		case STGOPER:
			inp=nextchar();
			//cout<<"242:stage oper pos "<<pos<<" inp "<<inp<<endl;
			if(cisoper(inp)){
				curr.setoper(inp);
			}else if(inp=='\0'){//str end
				if(!curr.getleft()->getisoper()){
					output(curr.getleft()->getnum());
					end();
				}else{//error
					ostringstream oss;
					oss<<"251:Maketree error, node "<<curr.getno()<<" pos "<<pos<<" stage oper,inp \\0.";
					error(oss.str());
				}
			}else{//error
				ostringstream oss;
				oss<<"256:Maketree error, node "<<curr.getno()<<" pos "<<pos<<" stage oper.";
				error(oss.str());
			}
//No break,continue to process
		case STGRIGHT:
			addright=newnode();
			inp=nextchar();
			//cout<<"261:stage right pos "<<pos<<" inp "<<inp<<endl;

			if(cisnum(inp)) {
				addright->setnum(getStrNum());
				curr.setright(addright);
			} else if(inp=='(') {
				addright->setinbrac(true);
				curr.setright(addright);
				//cout<<"270:node "<<curr.getno()<<" give to "<<addright->getno()<<endl;
				maketree(*addright);
			} else {
				ostringstream oss;
				oss<<"274:Maketree error, pos "<<pos<<",Stage right.";
				error(oss.str());
			}
//No break,continue to process

		default://STGENDING
			inp=nextchar();
			//cout<<"281:stage ending pos "<<pos<<" inp "<<inp<<endl;

			if(cisoper(inp)){

				addcomp=newnode();
				addcomp->setoper(inp);

				if(opcomp(curr.getoper(),inp)==HIGHER){
					//cout<<"291:Compare "<<curr.getoper()<<" higher than "<<inp<<endl;
					if(!curr.getisroot())
						if(curr.getisleft())
							curr.getfather()->setleft(addcomp);
						else
							curr.getfather()->setright(addcomp);

					addcomp->setinbrac(curr.getinbrac());
					curr.setinbrac(false);
					addcomp->setisroot(curr.getisroot());
					curr.setisroot(false);

					addcomp->setleft(&curr);

				}else{
					//cout<<"304:Compare "<<curr.getoper()<<" lower than "<<inp<<endl;
					addcomp->setleft(curr.getright());
					curr.setright(addcomp);
				}
				//cout<<"303:node "<<curr.getno()<<" give to "<<addcomp->getno()<<endl;
				maketree(*addcomp);
			}else if(inp!=')'&&inp!='\0'){
				ostringstream oss;
				oss<<"236:Maketree error, pos "<<pos<<",Stage ending.";
				error(oss.str());
			}
	}
	//cout<<"309:node "<<curr.getno()<<" returned."<<endl;
}

node* uptoroot(node *n){
	while(!n->getisroot()){
		//cout<<"316:Up node "<<n->getno()<<endl;
		n=n->getfather();
	}
	return n;
}

void deltree(){

	while(nodes.size()!=0){
		//cout<<"317:Del node "<<nodes.back()->getno()<<endl;
		delete nodes.back();
		nodes.pop_back();
	}
}

int calc(node &n){
	if(!n.getisoper()) return n.getnum();
	switch(n.getoper()){
		case '+':
			return calc(*n.getleft())+calc(*n.getright());
		break;
		case '-':
			return calc(*n.getleft())-calc(*n.getright());
		break;
		case '*':
			return calc(*n.getleft())*calc(*n.getright());
		break;
		case '/':
			return calc(*n.getleft())/calc(*n.getright());
		break;
	}
	ostringstream oss;
	oss<<"355:Calc error, node "<<n.getno()<<" oper "<<n.getoper();
	error(oss.str());
	return INVALID;
}

int main() {
	cout<<"Helix SStrict Calculator Beta"<<endl;

	cout<<"Input:"<<endl;
	cin>>str;
	pos=-1;

	check();

	node *n=newnode();
	n->setisroot(true);

	maketree(*n);
	n=uptoroot(n);
	output(calc(*n));
	deltree();
	cout<<"HSSCalc exit."<<endl;
	system("pause");
	return 0;
}
